|
In mathematics, a local language is a formal language for which membership of a word in the language can be determined by looking at a "window" of length two.〔Salomaa (1981) p.97〕 Equivalently, it is a language recognised by a local automaton, a class of deterministic finite automaton.〔Lawson (2004) p.130〕 Formally, we define a language ''L'' over an alphabet ''A'' to be ''local'' if there are subsets ''R'' and ''S'' of ''A'' and a subset ''F'' of ''A''×''A'' such that a word ''w'' is in ''L'' if and only if the first letter of ''w'' is in ''R'', the last letter of ''w'' is in ''S'' and no factor of length 2 in ''w'' is in ''F''.〔Lawson (2004) p.129〕 This corresponds to the regular expression〔〔Sakarovitch (2009) p.228〕 : More generally, a ''k''-''testable'' language ''L'' is one for which membership of a word ''w'' in ''L'' depends only on the prefix, suffix and the set of factors of ''w'' of length ''k''; a language is ''locally testable'' if it is ''k''-testable for some ''k''.〔McNaughton & Papert (1971) p.14〕 A local language is 2-testable.〔 ==Examples== * Over the alphabet 〔 : 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Local language (formal language)」の詳細全文を読む スポンサード リンク
|